# 给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
#
#  示例:
#
#  输入: [1,2,3,null,5,null,4]
# 输出: [1, 3, 4]
# 解释:
#
#    1            <---
#  /   \
# 2     3         <---
#  \     \
#   5     4       <---
#
#  Related Topics 树 深度优先搜索 广度优先搜索
#  👍 305 👎 0


# leetcode submit region begin(Prohibit modification and deletion)
# Definition for a binary tree node.
from typing import List


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        # 层次遍历，每次取最后一个节点的值加入结果
        # if not root:
        #     return []
        # nodes = []
        #
        # nodes.append(root)
        #
        # res = []
        # # 每层遍历，每次该层的最后一个节点
        # while len(nodes) != 0:
        #     last = nodes[len(nodes) - 1]
        #     res.append(last.val)
        #     tmp = []
        #     for node in nodes:
        #         if node.left:
        #             tmp.append(node.left)
        #         if node.right:
        #             tmp.append(node.right)
        #
        #     nodes = tmp
        #
        # return res

        # 深度遍历，每次访问当前节点，然后右子数，左子树
        def dfs(node, depth, res):
            if not node:
                return

            if depth == len(res):
                res.append(node.val)

            depth += 1
            dfs(node.right, depth, res)
            dfs(node.left, depth, res)

        res = []
        dfs(root, 0, res)
        return res

# leetcode submit region end(Prohibit modification and deletion)
